#include "Group.h"
#include "Helpers.h"
#include <math.h>

using std::set;
using std::vector;

/*****************************************************************************/
// Group
// a container for vertices that were chosen to be in a maximal independent set.
// vertices in the Group are unique (no two vertices with the same name)
// the vertices are organized in a stack data structure 
// to maintain the order of insertion
// the vertices are accessible by name through a map data structure
//
/*****************************************************************************/

//-----------------------------------------------------------------------------
// Ctor
// Creates a new Group object.
//
// @param name
//		the identifier of the group
// @param dir
//		the directory that this group will work with 
//		(from where the group will take it's vertices)
//		if dir is NULL the group will use the global static directory.
//-----------------------------------------------------------------------------
Group::Group(int name, VertexDirectory* dir)
{
	m_GroupName = name;
	m_Directory = dir;
}

//-----------------------------------------------------------------------------
// Copy Ctor
// initializes a new Group object from a given existing Group object.
//
// @param groupToCopy
//		the existing Group object to initialize from
// @param dir
//		the directory that the new group will work with 
//		(from where the group will take it's vertices)
//		if dir is NULL the group will use the global static directory.
//-----------------------------------------------------------------------------
Group::Group(Group& groupToCopy, VertexDirectory* dir)
{
	ListIterator listIt = groupToCopy.GetGroupVertices()->begin();
	ListIterator endListIt = groupToCopy.GetGroupVertices()->end();
	for (; listIt != endListIt; listIt++)
	{
		Vertex* vertex = *listIt;
		vertex = VertexDirectory::GetVertexFromDirectory((*listIt)->Name(),dir);
		vertex->Copy(*listIt);
		m_VerticesQueue.push_back(vertex);

		ListIterator *it = new ListIterator(m_VerticesQueue.end()); // init an iterrator to the recently added element
		(*it)--;
		// Vertex iterator to the map
		pair<MapIterator, bool> res;
		res = m_VerticesMap.insert(pair<VertexKey, ListIterator*>(vertex->Name(), it));
		if (res.second == false)
		{
			m_VerticesQueue.pop_front();
			throw (new GraphColoringException("insert vertex into map failed"));
		}
		//update the vertex to point to this group as its current container
		// do not update neighbours, we assume data in directory is already correct
		vertex->MoveToContainer(this, false, false);
	}
	m_GroupName = Algorithms::_TEMP_GROUP_NAME;
	m_Directory = dir;
}

//---------------------------------------------------------------------------------
// Clone 
// deep copy. Replaces all the group vertices with the vertices in groupToCopy.
// vertex pointers are taken from the vertex directory associated with this group
// (if no vertex directory is associated with this group - then from the static
// vertex directory)
//
// @param groupToCopy
//		the group object to copy it's vertices.
//---------------------------------------------------------------------------------
void Group::Clone(Group& groupToCopy)
{
	//clear the current queues
	m_VerticesQueue.clear();
	m_VerticesMap.clear();
	ListIterator listIt = groupToCopy.GetGroupVertices()->begin();
	ListIterator endListIt = groupToCopy.GetGroupVertices()->end();
	for (; listIt != endListIt; listIt++)
	{
		Vertex* vertex;
		if (m_Directory == NULL)
		{	// no vertex directory associated with this group - use the static directory
			vertex = VertexDirectory::GetStaticCopyVertex((*listIt)->Name());
		}
		else
		{	// use the vertex directory associated with this group
			vertex = m_Directory->GetWorkingCopyVertex((*listIt)->Name());
		}
		m_VerticesQueue.push_back(vertex);

		ListIterator *it = new ListIterator(m_VerticesQueue.end()); // init an iterrator to the recently added element
		(*it)--;
		// Vertex iterator to the map
		pair<MapIterator, bool> res;
		res = m_VerticesMap.insert(pair<VertexKey, ListIterator*>(vertex->Name(), it));
		if (res.second == false)
		{
			m_VerticesQueue.pop_front();
			throw (new GraphColoringException("insert vertex into map failed"));
		}
		//update the vertex to point to this group as its current container
		vertex->MoveToContainer(this, false);
	}
}

//-----------------------------------------------------------------------------
// Destructor
// destroys a Group object and free all the memory that was allocated during 
// the construction.
//-----------------------------------------------------------------------------
Group::~Group()
{
	map<VertexKey, ListIterator*>::iterator it;
	for (it = m_VerticesMap.begin(); it != m_VerticesMap.end(); it++)
	{
		delete it->second;
	}	
}

//-----------------------------------------------------------------------------
// Size
// return the number of vertices in the group.
//
// @return int
//		the number of vertices in the group.
//-----------------------------------------------------------------------------
int Group::Size()
{
	return m_VerticesQueue.size();
}

//-----------------------------------------------------------------------------
// Iterator
// creates an iterator for the group vertices queue.
// the iterator is initialized to the beginning of the queue 
// (the last element to leave the queue)
//
// @return list<Vertex*>::iterator
//		the iterator for the Group vertex queue.
//-----------------------------------------------------------------------------
list<Vertex*>::iterator Group::Iterator()
{
	return m_VerticesQueue.begin();
}

//-----------------------------------------------------------------------------
// End
// returns true if the iterator given points to the end of the vertices queue.
//
// @param it
//		an iterator for of the groups queue.
//
// @return bool
//		true  - if the iterator points to the end of the the vertices queue.
//		false - if not.
//-----------------------------------------------------------------------------
bool Group::End(list<Vertex*>::iterator it)
{
	return (it == m_VerticesQueue.end());
}

//-----------------------------------------------------------------------------
// GetGrouproupName
// returns the identifier of the group.
//
// @return int
//		the identifier of the group.
//-----------------------------------------------------------------------------
int Group::GetGroupName()
{
	return m_GroupName;
}

//-----------------------------------------------------------------------------
// PrintName
// returns the identifier of the group as a string
//
// @return string
//		the identifier of the group as a string.
//-----------------------------------------------------------------------------
string Group::PrintName()
{
	if (m_GroupName== Algorithms::_TEMP_GROUP_NAME)
	{
		return "temp group";
	}
	char buf[10];
	_itoa_s(m_GroupName, buf, 10, 10);
	string ret(buf);
	return ret;
}

//-----------------------------------------------------------------------------
// SetGrouproupName 
// sets the identifier of the group to the given value.
//
// @param newName
//		the new identifier of the group.
//
// @return int
//		returns the new assigned group identifier.
//-----------------------------------------------------------------------------
int Group::SetGroupName(int newName)
{
	m_GroupName = newName;
	return m_GroupName;
}

//-----------------------------------------------------------------------------
// InsertNewVertex
// overriding VertexContainer::InsertNewVertex
// Adds a new vertex to the group.
// note:	this function calls the function
//			InsertVertex(Vertex* vertex).
//
// @param vertexBase
//		the new vertex to add to the Group 
//		(note that this has to be a VertexBase object)
//-----------------------------------------------------------------------------
void Group::InsertNewVertex(VertexBase* vertexBase)
{
	Vertex *vertex = dynamic_cast<Vertex*>(vertexBase);
	if (vertex == NULL)
	{
		// if this isn't a vertex, this is a vertex set
		VertexSet *vertexSet = dynamic_cast<VertexSet*>(vertexBase);
		InsertNewVertexCouple(vertexSet);
		return;
	}
	else
	{
		InsertVertex(vertex);
	}
}

//-----------------------------------------------------------------------------
// InsertVertex
// Adds a new vertex to the group.
//
// @param vertex
//		the new vertex to add to the Group.
//-----------------------------------------------------------------------------
void Group::InsertVertex(Vertex* vertex)
{	
	if (!vertex->IsInGraph() && vertex->GetContainer() != NULL)
	{
		throw new GraphColoringException("Inserting a vertex from 1 group to another!");
	}

	// insert the vertex to the Queue
	m_VerticesQueue.push_front(vertex);
	ListIterator queueStart = m_VerticesQueue.begin();
	ListIterator *it = new ListIterator(queueStart); // init an iterrator to the recently added element
	if (it == NULL)	//memory allocation failed
	{
		Logger::LogMessage("ERROR: memory allocation failed in Group::InsertVertex. Vertex wasn't removed.");
		return;
	}
	
	// Vertex iterator to the map
	pair<MapIterator, bool> res;
	res = m_VerticesMap.insert(pair<VertexKey, ListIterator*>(vertex->Name(), it));
	if (res.second == false)
	{
		m_VerticesQueue.pop_front();
		throw (new GraphColoringException("insert vertex into map failed"));
	}		
	vertex->MoveToContainer(this, false);
	
	return;
}

//-----------------------------------------------------------------------------
// InsertNewVertexCouple
// Inserts a pair of vertices to the group
//
// @param vertices
//		the new pair of vertices to insert.
//-----------------------------------------------------------------------------
void Group::InsertNewVertexCouple(VertexSet* vertices)
{
	InsertNewVertex(vertices->Vertex1());
	InsertNewVertex(vertices->Vertex2());
}

//-----------------------------------------------------------------------------
// RemoveVertexBase 
// removes a vertex from the group.
// note:	this function calls the function
//			RemoveVertex(Vertex* vertex).
//
// @param vertexBase
//		the vertex object to remove.
//		(note that this has to be a VertexBase object)
//-----------------------------------------------------------------------------
void Group::RemoveVertexBase(VertexBase *vertexBase)
{
	Vertex *vertex = dynamic_cast<Vertex*>(vertexBase);
	if (vertex == NULL)
	{
		// if this isn't a vertex, this is a vertex set
		VertexSet *vertexSet = dynamic_cast<VertexSet*>(vertexBase);
		RemoveVertexSet(vertexSet);
		return;
	}
	else
	{
		RemoveVertex(vertex);
	}
}
//-----------------------------------------------------------------------------
// RemoveVertex
// removes the given vertex from the group.
//
// @param vertex
//		the vertex to remove from the group.
//-----------------------------------------------------------------------------
void Group::RemoveVertex(Vertex* vertex)
{
	MapIterator it = m_VerticesMap.find(vertex->Name());
	if ( it == m_VerticesMap.end())
		throw (new GraphColoringException("remove vertex failed - vertex not in group"));
	
	ListIterator toRemove = *(it->second);
	m_VerticesQueue.erase(toRemove);

	// the erase funcation checks if an element with this key dosent exsits.
	int res = m_VerticesMap.erase(vertex->Name());
	if(res <= 0)
	{
		throw (new GraphColoringException("remove vertex from map failed"));
	}	
	// vertex is now nowhere
	vertex->MoveToContainer(NULL, false);
}

//-----------------------------------------------------------------------------
// RemoveVertexSet
// removes a vertex couple from the group
//
// @param vertexSet
//		the vertex couple to remove from the group.
//-----------------------------------------------------------------------------
void Group::RemoveVertexSet(VertexSet *vertexSet)
{
	RemoveVertex(vertexSet->Vertex1());
	RemoveVertex(vertexSet->Vertex2());
}

//-----------------------------------------------------------------------------
// IsVertexBaseInGroup
// returns true if the vertex base object is a member of the group.
// note:	this function calls the function
//			IsVertexInGroup(VertexKey vertex).
// 
// @param vertexBase
//		the vertex to look for in the group
//		(note that this has to be a VertexBase object)
//
// @return bool
//		true - if a vertex with the provided name is a member of the group.
//		false - if not.
//-----------------------------------------------------------------------------
bool Group::IsVertexBaseInGroup(VertexBase *vertexBase)
{
	Vertex *vertex = dynamic_cast<Vertex*>(vertexBase);
	if (vertex == NULL)
	{
		// if this isn't a vertex, this is a vertex set
		VertexSet *vertexSet = dynamic_cast<VertexSet*>(vertexBase);
		if (vertexSet == NULL) // failed to cast the given object to a known vertex object
		{
			Logger::LogMessage("Group::ContainsVertexBase falied to cast the provided object to a vertex or vertex pair object.");
			return false;
		}
		return IsVertexCoupleInGroup(vertexSet);
	}
	else
	{
		return IsVertexInGroup(vertex->Name());
	}
}

//-----------------------------------------------------------------------------
// IsVertexInGroup 
// returns true iff a vertex with the provided name is a member of the group.
//
// @param vertex
//		the vertex to look for in the group.
//
// @return bool
//		true - if a vertex with the provided name is a member of the group.
//		false - if not.
//-----------------------------------------------------------------------------
bool Group::IsVertexInGroup(VertexKey vertex)
{
	MapIterator it = m_VerticesMap.find(vertex);
	if (m_VerticesMap.end() == it)
		return false;

	return true;
}

//-----------------------------------------------------------------------------
// IsVertexCoupleInGroup
// returns true iff both vertices in the vertex set are members of the group.
//
// @param vertexSet
//		the pair to look for in the group.
//
// @return bool
//		true - if both vertices in the vertex set are members of the group.
//		false - if not.
//-----------------------------------------------------------------------------
bool Group::IsVertexCoupleInGroup(VertexSet *vertexSet)
{
	return IsVertexInGroup(vertexSet->Vertex1()->Name()) || IsVertexInGroup(vertexSet->Vertex2()->Name());
}

//-----------------------------------------------------------------------------
// IsLegalToAdd 
// checks if it is legal to add the given vertex to the group.
// It is legal to add a vertex to the group if the group remains independant.
// (the vertices have no edges between them).
//
// @param vertex
//		the vertex we want to chek if it is legal to add
// @param makeInterchangeableChecks
//		perform interchangeable checks //TODO complete this with Ronni
//
// @return bool
//		true - if it is legal to add the given vertex to the group
//		false - if not.
//-----------------------------------------------------------------------------
bool Group::IsLegalToAdd(VertexBase* vertex, bool makeInterchangeableChecks)
{
	//first check that the vertex is not NULL
	if (vertex == NULL)
	{
		throw new GraphColoringException("Checking if a NULL vertex is legal to group");
	}

	// If this vertex has a neigbour in the group, it is illegal to add
	if (vertex->HasNeighbourInGroup(this))
	{
		return false;
	}

	if (makeInterchangeableChecks)
	{
		// Insert the vertex temporarily and check effects
		Graph *graph = vertex->GetContainingGraph();
		if (graph == NULL)
		{
			// If the graph is null, this vertex belongs to a group and is illegal to add
			Debug::PrintDebugMsg("Graph is null, returning false");
			return false;
		}

		// If this vertex is interchangeable, and this isn't the original group and it cannot be replaced by any other vertex
		// we can't add it to any group
		//if (vertex->Interchangeable() && ((VertexContainer*)this != vertex->GetPreviousContainer()) && !(vertex->CanBeReplaced()))
		if (vertex->Interchangeable() && !(vertex->CanBeReplaced()))
		{
			return false;
		}

		// If this vertex is a replacement vertex and adding it to a group will cause us to
		// return one of it's interchangeable vertices to an illegal group, we can't add 
		// it to any groups
		// If it is being returned to a group right now (chosen), we don't check this
		if (vertex->IsReplacement() && !(vertex->CanBeRemovedFromReplacements()))
		{
			return false;
		}

		if (!IsVertexBaseInGroup(vertex))
		{
			bool wasInGraph = vertex->IsInGraph();
	
			if (wasInGraph)
			{
				graph->RemoveVertexBase(vertex);
			}

			InsertNewVertex(vertex);
			Debug::PrintDebugMsg(vertex->PrintName()+ " is now in group");
			bool isOk = true;
			if (!vertex->CanAllRelatedInterchangeablesBeReplaced())
			{
				isOk = false;
			}
			RemoveVertexBase(vertex);

			if (wasInGraph)
			{
				graph->InsertVertexBase(vertex);
			}
						
					
			return isOk;
		} 
		else
		{
			// if vertex is already in group, we can't add it again
			return false;
		}
	} 

	return true;
}

//-----------------------------------------------------------------------------
// IsLegalToAdd for pair
// checks if it is legal to add the given vertex pair to the group.
// It is legal to add a vertex pair to the group if the group remains independant.
// (the all the group vertices have no edges between them).
//
// @param vertexPair
//		the vertex pair we want to chek if it is legal to add
// @param makeInterchangeableChecks
//		perform interchangeable checks //TODO complete this with Ronni
//
// @return bool
//		true - if it is legal to add the given vertex pair to the group
//		false - if not.
//-----------------------------------------------------------------------------
bool Group::IsLegalToAdd(pair<Vertex*, Vertex*> &vertexPair, bool makeInterchangeableChecs)
{
	return (IsLegalToAdd(vertexPair.first, makeInterchangeableChecs) && IsLegalToAdd(vertexPair.second, makeInterchangeableChecs));
}

//-----------------------------------------------------------------------------
// BreakGroup
// Breaks the current group and creates a new group without some of its last 
// vertices, as calculated by the percent given.
//
// @parameter percent
//		the percent of the vertices to keep in the group
// @parmeter thrownVertices
//		if not NULL, this list will contain a list of the vertices that
//		were removed from the group
// @parmeter newGroupDirectory
//		if not NULL, the vertices returned (in the group object returned from the method, 
//		and in thrownVertices) will be from newGroupDirectory directory. Otherwise, they 
//		will be from the directory associated with this group
//
// @return Group*
//		a new group which is a copy of the current group, 
//		with percent of vertices removed from it.
//-----------------------------------------------------------------------------
Group* Group::BreakGroup(double percent, list<Vertex*>* thrownVertices, VertexDirectory* newGroupDirectory)
{

	VertexDirectory* dir = newGroupDirectory;
	if (dir == NULL)
	{	// work with the directory associated with this group
		dir = m_Directory;
	}
	Group *newGroup;
	try
	{
		newGroup = new Group(*this, dir);
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		Logger::LogMessage("memory allocation failed in Group::BreakGroup. group wasn't created.");
		return NULL;
	}
	
	int numberToPop = this->Size() - (int)floor((Size() * percent) / 100);

	
	for(; numberToPop > 0; numberToPop--)
	{
		Vertex* out = newGroup->m_VerticesQueue.front();
		newGroup->m_VerticesQueue.pop_front();
		newGroup->m_VerticesMap.erase(out->Name());
		if(thrownVertices != NULL)
		{
			thrownVertices->push_front(out);
		}
	}

	return newGroup;
}

//-----------------------------------------------------------------------------
// SetGroupVertexDirectory 
// set the directory this group will use to the given directory
//
// @param dir
//		the directory to associate with this group.
//-----------------------------------------------------------------------------
void Group::SetGroupVertexDirectory(VertexDirectory* dir)
{
	m_Directory = dir;
}

//-----------------------------------------------------------------------------
// VerticesNames 
// returns a list of all vertex names in the group
//
// @return list<VertexKey>
//		the list of the group vertices.
//-----------------------------------------------------------------------------
list<VertexKey> Group::VerticesNames()
{
	list<VertexKey> names;
	MapIterator it;
	for (it = m_VerticesMap.begin(); it != m_VerticesMap.end(); it++)
	{
		names.insert(names.begin(),it->first);
	}	
	return names;
}

//-----------------------------------------------------------------------------
// Find 
// returns an iterator to a vertex object with the given name
//
// @param vertexName
//		the vertex name
//
// @return list<Vertex*>::iterator
//		an iterator to a vertex object in the group queue with the given name.
//		if no such vertex in the queue - 
//		an iterator to the end of the queue is returned.
//-----------------------------------------------------------------------------
list<Vertex*>::iterator Group::Find(VertexKey vertexName)
{
	MapIterator it = m_VerticesMap.find(vertexName);
	if (it == m_VerticesMap.end())
	{
		return m_VerticesQueue.end();
	} else 
	{
		return *(it->second);
	}
}

//-----------------------------------------------------------------------------
// GetGroupVertices
// returns a list of pointers to all the vertices in the group
// (returns the group queue)
//
// @return list<Vertex*>*
//		the vertex queue of the group.
//-----------------------------------------------------------------------------
list<Vertex*>* Group::GetGroupVertices()
{
	return (&m_VerticesQueue);
}


//----------------------------------------------------------------------------------
// Print
// prints all vertices of the group.
//----------------------------------------------------------------------------------
void Group::Print()
{
	list<VertexKey> names = VerticesNames();
	list<VertexKey>::iterator it;
	string str = "\n";
	for (it=names.begin(); it != names.end(); it ++)
	{
		
		VertexKey vertexName = *it;
		for (unsigned int i=0; i< vertexName.size(); i++)
		{
			if ((vertexName)[i])
			{
				str += "1";
			}
			else
			{
				str += "0";
			}
		}
		str += "\n";
	}

	Logger::LogMessage(str);
}

//----------------------------------------------------------------------------------
// PairUpVerticesAndFindReplacements 
// Creates all vertex sets from group and finds their replacements
//
// @param graph
//		TODO complete with Ronni
//----------------------------------------------------------------------------------
void Group::PairUpVerticesAndFindReplacements(Graph *graph)
{
	ListIterator it = m_VerticesQueue.begin();
	while (it != m_VerticesQueue.end())
	{
		Vertex *vertex1 = *it;
		it++;
		if (it != m_VerticesQueue.end())
		{
			Vertex *vertex2 = *it;
			it++;
			VertexSet *newSet = new VertexSet(vertex1, vertex2);
			vertex1->SetContaingVertexSet(newSet);
			vertex2->SetContaingVertexSet(newSet);
			Debug::PrintDebugMsg("finding replacements for set "+newSet->PrintName());
			// Find replacements for this set
			newSet->FindReplacements(graph);
			
			// If this set isn't interchangeable after all, it is not
			// in the directory and we don't need to save it
			if (!newSet->Interchangeable())
			{
				vertex1->SetContaingVertexSet(NULL);
				vertex2->SetContaingVertexSet(NULL);
				delete newSet;
			} 
			
		}
	}	
}